namespace AdvancedTraining.Lesson48;

/// <summary>
/// 迷宫III算法 - LeetCode 499
/// 使用BFS寻找球从起点到终点的最短路径，球碰到墙壁会停止，可以选择改变方向
/// 返回字典序最小的最短路径
/// </summary>
public class TheMazeIii
{
    /// <summary>
    /// 方向数组：下、左、右、上、停止
    /// </summary>
    private static readonly int[][] To =
    [
        [1, 0],   // 下 (down)
        [0, -1],  // 左 (left)
        [0, 1],   // 右 (right)
        [-1, 0],  // 上 (up)
        [0, 0]    // 停止
    ];

    /// <summary>
    /// 方向字符数组
    /// </summary>
    private static readonly string[] Re = ["d", "l", "r", "u"];

    /// <summary>
    /// 寻找从球到洞的最短路径
    /// 时间复杂度：O(N * M * 4)，其中N和M是迷宫的行数和列数
    /// 空间复杂度：O(N * M * 4)，用于存储访问状态
    /// </summary>
    /// <param name="maze">迷宫，0表示空地，1表示墙</param>
    /// <param name="ball">球的起始位置[行, 列]</param>
    /// <param name="hole">洞的位置[行, 列]</param>
    /// <returns>最短路径字符串，如果无法到达则返回"impossible"</returns>
    public static string FindShortestWay(int[,] maze, int[] ball, int[] hole)
    {
        var n = maze.GetLength(0);
        var m = maze.GetLength(1);
        Node[] q1 = new Node[n * m], q2 = new Node[n * m];
        int s1 = 0, s2 = 0;
        var visited = new bool[n, m, 4];
        s1 = Spread(maze, n, m, new Node(ball[0], ball[1], 4, ""), visited, q1, s1);
        while (s1 != 0)
        {
            for (var i = 0; i < s1; i++)
            {
                var cur = q1[i];
                if (hole[0] == cur.R && hole[1] == cur.C) return cur.P;
                s2 = Spread(maze, n, m, cur, visited, q2, s2);
            }

            (q1, q2) = (q2, q1);
            s1 = s2;
            s2 = 0;
        }

        return "impossible";
    }

    /// <summary>
    /// 扩展当前节点的所有可能状态
    /// maze迷宫，走的格子
    /// n 行数
    /// m 列数
    /// 当前来到的节点，cur -> (r,c) 方向 路径（决定）
    /// v [行,列,方向] 一个格子，其实在宽度有限遍历时，是4个点！
    /// q 下一层的队列
    /// s 下一层队列填到了哪，size
    /// 当前点cur，该分裂分裂，该继续走继续走，所产生的一下层的点，进入q，s++
    /// 返回值：q增长到了哪？返回size -> s
    /// </summary>
    /// <param name="maze">迷宫</param>
    /// <param name="n">行数</param>
    /// <param name="m">列数</param>
    /// <param name="cur">当前节点</param>
    /// <param name="v">访问状态数组</param>
    /// <param name="q">队列</param>
    /// <param name="s">队列大小</param>
    /// <returns>新的队列大小</returns>
    private static int Spread(int[,] maze, int n, int m, Node cur, bool[,,] v, Node[] q, int s)
    {
        var d = cur.D;
        var r = cur.R + To[d][0];
        var c = cur.C + To[d][1];
        // 分裂去！
        if (d == 4 || r < 0 || r == n || c < 0 || c == m || maze[r, c] != 0)
        {
            for (var i = 0; i < 4; i++)
                if (i != d)
                {
                    r = cur.R + To[i][0];
                    c = cur.C + To[i][1];
                    if (r >= 0 && r < n && c >= 0 && c < m && maze[r, c] == 0 && !v[r, c, i])
                    {
                        v[r, c, i] = true;
                        var next = new Node(r, c, i, cur.P + Re[i]);
                        q[s++] = next;
                    }
                }
        }
        else
        {
            // 不分裂！继续走！
            if (!v[r, c, d])
            {
                v[r, c, d] = true;
                q[s++] = new Node(r, c, d, cur.P);
            }
        }

        return s;
    }

    /// <summary>
    /// 节点：来到了哪？(r,c)这个位置
    /// 从哪个方向来的！d -> 0 1 2 3 4
    /// 之前做了什么决定让你来到这个位置。
    /// </summary>
    public class Node(int row, int col, int dir, string path)
    {
        /// <summary>
        /// 列坐标
        /// </summary>
        public readonly int C = col;

        /// <summary>
        /// 方向：0=下, 1=左, 2=右, 3=上, 4=停止
        /// </summary>
        public readonly int D = dir;

        /// <summary>
        /// 路径字符串
        /// </summary>
        public readonly string P = path;

        /// <summary>
        /// 行坐标
        /// </summary>
        public readonly int R = row;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 迷宫III算法测试 ===");

        // 测试用例1：LeetCode官方示例1
        var maze1 = new int[,] {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 1, 1},
            {0, 0, 0, 0, 0}
        };
        var ball1 = new[] {0, 4};
        var hole1 = new[] {4, 4};
        var result1 = FindShortestWay(maze1, ball1, hole1);

        Console.WriteLine("测试用例1:");
        Console.WriteLine("迷宫大小: " + maze1.GetLength(0) + "x" + maze1.GetLength(1));
        Console.WriteLine("球位置: [" + ball1[0] + ", " + ball1[1] + "]");
        Console.WriteLine("洞位置: [" + hole1[0] + ", " + hole1[1] + "]");
        Console.WriteLine("结果: \"" + result1 + "\"");
        Console.WriteLine("预期: \"lul\" 或 \"ul\"");
        Console.WriteLine("匹配: " + (result1 == "lul" || result1 == "ul"));
        Console.WriteLine();

        // 测试用例2：LeetCode官方示例2
        var maze2 = new int[,] {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 1, 1},
            {0, 0, 0, 0, 0}
        };
        var ball2 = new[] {0, 4};
        var hole2 = new[] {3, 2};
        var result2 = FindShortestWay(maze2, ball2, hole2);

        Console.WriteLine("测试用例2:");
        Console.WriteLine("球位置: [" + ball2[0] + ", " + ball2[1] + "]");
        Console.WriteLine("洞位置: [" + hole2[0] + ", " + hole2[1] + "]");
        Console.WriteLine("结果: \"" + result2 + "\"");
        Console.WriteLine("预期: \"impossible\"");
        Console.WriteLine("匹配: " + (result2 == "impossible"));
        Console.WriteLine();

        // 测试用例3：简单路径
        var maze3 = new int[,] {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };
        var ball3 = new[] {0, 0};
        var hole3 = new[] {2, 2};
        var result3 = FindShortestWay(maze3, ball3, hole3);

        Console.WriteLine("测试用例3: 简单路径");
        Console.WriteLine("球位置: [" + ball3[0] + ", " + ball3[1] + "]");
        Console.WriteLine("洞位置: [" + hole3[0] + ", " + hole3[1] + "]");
        Console.WriteLine("结果: \"" + result3 + "\"");
        Console.WriteLine("有效路径: " + (result3 != "impossible"));
        Console.WriteLine();

        // 测试用例4：起点即终点
        var maze4 = new int[,] {
            {0, 0},
            {0, 0}
        };
        var ball4 = new[] {1, 1};
        var hole4 = new[] {1, 1};
        var result4 = FindShortestWay(maze4, ball4, hole4);

        Console.WriteLine("测试用例4: 起点即终点");
        Console.WriteLine("球位置: [" + ball4[0] + ", " + ball4[1] + "]");
        Console.WriteLine("洞位置: [" + hole4[0] + ", " + hole4[1] + "]");
        Console.WriteLine("结果: \"" + result4 + "\"");
        Console.WriteLine("预期: \"\" (空字符串)");
        Console.WriteLine("匹配: " + (result4 == ""));
        Console.WriteLine();

        // 测试用例5：无法到达
        var maze5 = new int[,] {
            {0, 1, 0},
            {1, 1, 0},
            {0, 0, 0}
        };
        var ball5 = new[] {0, 0};
        var hole5 = new[] {2, 2};
        var result5 = FindShortestWay(maze5, ball5, hole5);

        Console.WriteLine("测试用例5: 无法到达");
        Console.WriteLine("球位置: [" + ball5[0] + ", " + ball5[1] + "]");
        Console.WriteLine("洞位置: [" + hole5[0] + ", " + hole5[1] + "]");
        Console.WriteLine("结果: \"" + result5 + "\"");
        Console.WriteLine("预期: \"impossible\"");
        Console.WriteLine("匹配: " + (result5 == "impossible"));
        Console.WriteLine();

        // 测试用例6：单格迷宫
        var maze6 = new int[,] {
            {0}
        };
        var ball6 = new[] {0, 0};
        var hole6 = new[] {0, 0};
        var result6 = FindShortestWay(maze6, ball6, hole6);

        Console.WriteLine("测试用例6: 单格迷宫");
        Console.WriteLine("球位置: [" + ball6[0] + ", " + ball6[1] + "]");
        Console.WriteLine("洞位置: [" + hole6[0] + ", " + hole6[1] + "]");
        Console.WriteLine("结果: \"" + result6 + "\"");
        Console.WriteLine("预期: \"\" (空字符串)");
        Console.WriteLine("匹配: " + (result6 == ""));
        Console.WriteLine();

        Console.WriteLine("=== 测试完成 ===");
        Console.WriteLine();
        Console.WriteLine("算法说明:");
        Console.WriteLine("1. 使用BFS进行广度优先搜索");
        Console.WriteLine("2. 球会沿着一个方向滚动直到撞墙");
        Console.WriteLine("3. 在每个位置可以选择改变方向");
        Console.WriteLine("4. 返回字典序最小的最短路径");
        Console.WriteLine("5. 方向优先级: d < l < r < u (按字母顺序)");
    }
}